package 树;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Demo10 {
    /*
    * 方法一: 广度优先遍历(bfs)
    * */
    static class Solution {
        public List<Double> averageOfLevels(TreeNode root) {
            List<Double> list = new ArrayList<>();
            if(root == null){
                return list;
            }
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            while(!queue.isEmpty()){
                int levelCount = queue.size();
                double avg = 0;
                for(int i = 0; i<levelCount; i++){
                    TreeNode node = queue.poll();
                    avg+=node.val;
                    if(node.left != null) queue.add(node.left);
                    if(node.right != null) queue.add(node.right);
                }
                avg/=levelCount;
                list.add(avg);
            }
            return list;
        }
    }
    /*
    * 方法二: 思路 用变量记录该节点所在的层数,如果碰到某个节点的层数和当前节点的层数相同,把两个的值加到一起
    * */
}
